package com.niuke;

import com.pojo.ListNode;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-12-09 18:24:12
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-12-09     张李鑫                     1.0         1.0 Version
 */
public class JZ52 {
    /**
     * 输入两个无环的单向链表，找出它们的第一个公共结点，
     * 如果没有公共节点则返回空。（注意因为传入数据是链表，
     * 所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
     */
    public static ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        ListNode loop1 = pHead1;
        ListNode loop2 = pHead2;

        int count = 0;
        while (loop1.next != null) {
            loop1 = loop1.next;
            count++;
        }

        while (loop2.next != null) {
            loop2 = loop2.next;
            count--;
        }

        if (loop1 != loop2) {
            return null;
        }
        loop1 = count > 0 ? pHead1 : pHead2;
        loop2 = loop1 == pHead1 ? pHead2 : pHead1;

        count= Math.abs(count);
        while (count > 0) {
            loop1=loop1.next;
            count--;
        }


        while (loop1 != loop2) {
            loop1 = loop1.next;
            loop2 = loop2.next;
        }
        return loop1;
    }

    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        ListNode listNode1 = new ListNode(4);
        ListNode listNode2 = new ListNode(5);
        ListNode listNode3 = new ListNode(6);
        ListNode listNode4 = new ListNode(7);


        listNode.next=listNode3;
        listNode3.next=listNode4;

        listNode1.next=listNode2;
        listNode2.next=listNode3;


        System.out.println(FindFirstCommonNode(listNode, listNode1));


    }

}
